$ n \in \mathbb{N}$
一変数で考える（簡単化）
入力のサイズ $ n $ を大きくしていったときの計算量 $ f(n) $ の振る舞いを調べる
関数 $ g(n) $ と２つの定数 $ n_0, c $が存在し， $ n \gt n_0 $ である $ n $ に対して，常に
\begin{align} f(n) \leq c g(n) \Rightarrow f(n) = O(g(n)) \end{align}と表現し， $ f(n) $ の計算量はオーダー $ O(g(n)) $であるという．
対角要素が非負 -> 自己ループを持つ
講義では，辺は [行] から [列]
実データでは...データがでかすぎるので，グラフが作れない．
null: 門番
隣接行列の１つの行について１つの連結リスト
int main() {
int StartRoom = 0;
dfs(StartRoom);
return 0;
}
void dfs(CurrentRoom) {
int RoomToGo;
// indicates we have visited <CurrentRoom>
visited[CurrentRoom] = 1;
for (RoomToGo = 0; RoomToGo < N; RoomToGo++) {
if (edge[CurrentRoom][RoomToGo] != 0 && // We can go to <RoomToGo> from <CurrentRoom>
visited[RoomToGo]) == 0 { // We have not visited <RoomToGo>
dfs(RoomToGo);
}
}
}
時間計算量: Step数 \begin{align} O(N * N) \end{align}
空間計算量: 使ったメモリの数
ケチれないの？# define N 8
int edge[N][N] = {{...}, {...}, ...}
int main() {
int StartNode = 0;
bfs(StartNode);
return 0;
}
void bfs(int StartNode) {
int listed[N] = {0, 0, ...}; // みつけたらチェック
int queue[N];
int qhead[N];
int qtail[N];
int CurrentNode; // ループ変数
int NodeToCheck; // ループ変数
listed[StartNode] = 1;
// enqueue
queue[qtail++] = StartNode;
while (qhead < qtail) {
// dequeue
CurrentNode = queue[qhead++];
for (NodeToCheck = 0; NodeToCheck < N; NodeToCheck++) {
if (edge[CurrentNode][NodeToCheck] != 0 && \
listed[NodeToCheck] == 0) {
// enqueue
queue[qtail++] = NodeToCheck;
listed[NodeToCheck] = 1;
}
}
}
}
全順序
半順序
数学科と情報科学科の学生二人の成績は比較不可能
有向グラフ
探索アルゴリズムを使って実現できる．
int edge[8][8] = {
{0, 1, 0, 0, 1, 0, 0, 0},
{0, 1, 0, 0, 0, 0, 1, 0},
{0, 0, 0, 1, 0, 0, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 0, 1, 0, 0},
{0, 0, 0, 0, 0, 0, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 0, 0, 0, 0}
};
int visited[8];
int N = 8;
int CurrentNode;
void topologicalsort(int CurrentNode) {
int NodeToGo;
visited[CurrentNode] = 1;
for (NodeToGo = 0; NodeToGo < N; NodeToGo++) {
if (edge[CurrentNode][NodeToGo] != 0 && \
visited[NodeToGo] == 0) {
topologicalsort(NodeToGo);
}
}
// ?
printf("%d", CurrentNode);
}
int main() {
for (int StartNode = 0; StartNode < N; StartNode++) {
topologicalsort(StartNode);
}
}
貪欲法は一般に全体最適なアルゴリズムではないが，ダイクストラ法は必ず全体最適に到達する例外的なアルゴリズム
# include <iostream>
# define INF 2<<10
# define N 6
int edge[N][N] = {
{0, INF, INF, 8, 15, INF},
{10, 0, 24, INF, 8, INF},
{INF, INF, 0, INF, INF, 6},
{INF, INF, INF, 0, 5, INF},
{INF, INF, 12, INF, 0, 7},
{INF, INF, 3, INF, INF, 0}
};
// 経路を保存する配列 (重みが正なので閉路に落ちない -> 配列のサイズはNで足りる)
int cost[N];
// 札 (これをたどっていけば最短経路がわかる)
int from[N];
// 未処理の頂点を保存する配列
int setU[N];
// setUの0からいくつまでのデータがまだ未処理である
//
// if numU = 2 then
// setU[0], setU[1] are not processed yet
//
int numU = N;
int min_node_index, min_node, min_cost;
void find_shortest_dijkstra(int StartNode) {
for (int u = 0; u < N; u++) {
setU[u] = u;
}
for (int x = 0; x < N; x++) {
cost[x] = edge[StartNode][x];
from[x] = StartNode;
}
setU[StartNode] = setU[numU-1];
numU--;
// 未処理のデータがまだ存在すれば繰り返し
for (; numU > 0; numU--) {
min_node_index = 0;
min_node = setU[min_node_index];
min_cost = cost[min_node];
for (int u = 1; u < numU; u++) {
if (cost[setU[u]] < min_cost) {
min_node_index = u;
min_node = setU[min_node_index];
min_cost = cost[min_node];
}
}
setU[min_node_index] = setU[numU - 1];
for (int u = 0; u < numU - 1; u++) {
if (edge[min_node][setU[u]] > 0 &&
cost[setU[u]] > cost[min_node] + edge[min_node][setU[u]]) {
cost[setU[u]] = cost[min_node] + edge[min_node][setU[u]];
from[setU[u]] = min_node;
}
}
}
}
int main() {
find_shortest_dijkstra(0);
std::cout << cost[4] << std::endl;
// 最短経路の復元
std::cout << from[4] << std::endl;
std::cout << from[3] << std::endl;
}
DijkstraをN回回しても良いが...
動的計画法に基づくアルゴリズム
最短距離を求めるアルゴリズム 経由しても良いという制約．（下にいくほど難しい）
for (int k = 0; k < N; k++) {
for (int i = 0; i < N; i++) {
for (int = 0; j < N; j++) {
d[i][j] = min(d[i][j], d[i][k] + d[k][j])
}
}
}
をするだけでは経路がわからない．
経路行列(N * N)を持つことで経路も表示できる．
経路行列に対して再帰呼び出しを行うと良い
ループが展開可能なので，並列に計算することで高速に求解できる．